package oct2013;

public class LongestPalindromicSubstring {
	public String longestPalindrome(String s) {
		int n = s.length();
		int[] ch = new int[n * 2 + 1];
		for (int i = 0; i < n; ++i) {
			ch[i * 2 + 1] = s.charAt(i);
		}
		int[] dp = new int[n * 2 + 1];
		int max = 0;
		int id = 0;
		for (int i = 1; i < n * 2 + 1; ++i) {
			if (dp[max] + max >= i) {
				dp[i] = Math.min(dp[max * 2 - i], dp[max] + max - i);
			}
			while (i + dp[i] + 1 < n * 2 + 1 && i - dp[i] - 1 >= 0
					&& ch[i + dp[i] + 1] == ch[i - dp[i] - 1])
				dp[i]++;
			if (dp[max] + max < dp[i] + i)
				max = i;
			if (dp[i] > dp[id])
				id = i;
		}
		StringBuilder sb = new StringBuilder();
		for (int i = id - dp[id]; i < id + dp[id]; i += 2) {
			sb.append((char) ch[i + 1]);
		}
		return sb.toString();
	}

	public String longestPalindromeNaive(String s) {
		int n = s.length();
		String res = "";
		for (int i = 0; i < n; ++i) {
			int j = 0;
			while (i >= j && i + j < n && s.charAt(i - j) == s.charAt(i + j))
				j++;
			if (res.length() < j + j - 1) {
				res = s.substring(i - j + 1, i + j);
			}
			j = 0;
			while (i - j - 1 >= 0 && i + j < n
					&& s.charAt(i - j - 1) == s.charAt(i + j))
				j++;
			if (res.length() < j + j) {
				res = s.substring(i - j, i + j);
			}
		}
		return res;
	}

	public static void main(String[] args) {
		LongestPalindromicSubstring a = new LongestPalindromicSubstring();
		a.longestPalindrome("bb");
	}
}
